A typical network router includes a utility which allows a system administrator to trace a route from the router, i.e., a source computer, to a target computer. That is, this route tracing utility identifies nodes which form a network path from the source computer to the target computer. In a network which uses Transmission Control Protocol/Internet Protocol (TCP/IP), it is common for each router to include a route tracing utility called “traceroute”.
In one implementation, the route tracing utility is a command line program which prompts the system administrator for a domain name that identifies the target computer. In response to the domain name, the route tracing utility returns an output including a list of routers (e.g., the domain names and/or IP addresses of the routers) which extend along a path between the source computer and the target computer. In some implementations, the output further includes roundtrip times for IP packets to travel from the source computer to the routers, and for associated response messages to travel from the routers back to the source computer.
It is common for the route tracing utility to use a Time-To-Live (TTL) network feature such as that of TCP/IP networks. This TTL feature was implemented to resolve a drawback of early TCP/IP networks. In such networks, a configuration anomaly within a router could cause packets to follow an endless loop within the network. That is, the packets would move from router to router in a circle and never leave the network. Over time, the number of packets travelling in this loop would accumulate to the point that the routers in the loop would suffer from performance degradation and become unable to route non-looping packets in a timely manner.
To overcome this drawback, a TTL field was added to IP packets. The contents of the TTL field of a packet indicate the number of network nodes that can process that packet before that packet is deemed stale and removed from the network. The following is a more detailed explanation of how the TTL field is used.
When a source computer attempts to send a packet to a target computer along a path of routers, the source computer initializes the contents of the TTL field of the packet to an initial value (e.g., between 0 and 255) prior to sending the packet along the path toward the target computer. The first router to receive the packet decrements the contents of the TTL field of the packet, and determines whether the packet is stale by comparing the decremented contents to a predetermined value (e.g., 0 or 1). If the packet is stale, the first router removes the packet from the network and sends an Internet Control Message Protocol (ICMP) error message back to the source computer to indicate that the first router has removed the packet from the network. However, if the packet is not stale, the first router forwards the packet to the next router along the path leading to the target computer. The next router then processes the packet in a similar manner, and so on, until the packet arrives at the target computer, or until a router along the path removes the packet because the packet has become stale. Accordingly, any packet which is endlessly caught in a loop inevitably will become stale (as routers decrement its TTL field contents) and be removed from the network by a router.
At the source computer, when a system administrator invokes a route tracing utility which relies on the above-described TTL feature, the system administrator typically provides the route tracing utility with a domain name identifying a target computer. In response, the route tracing utility generates a packet and sets the TTL field of that packet initially to 1. Then, the route tracing utility sends that packet from the source computer, to the target computer. Assuming that the first router to receive the packet is a node (e.g., a data communications device) other than the target computer, the first router receiving the packet decrements the contents of the TTL field and determines that the packet is stale (e.g., the TTL contents now equal 0). Accordingly, the first router removes the packet from the network and sends an ICMP message back to the source computer. The source computer is able to identify the first router as the first node along the path leading to the target computer (e.g., from address information in the header of the ICMP error message), and the round trip time (e.g., by calculating the difference between the time the source computer sends the packet and the time the source computer receives the ICMP error message.
The source computer then generates another packet and sets the TTL field of that packet to 2. The source computer then sends that packet toward the target computer along the path. When the first router receives that packet, the first router decrements the contents of the TTL field and determines that the packet is not stale (e.g., the TTL contents are greater than 0). Accordingly, the first router identifies the second router on the path leading to the target computer, and sends the packet to the second router. When the second router receives and processes the packet, the second router determines that the packet is now stale, removes the packet from the network, and sends an ICMP error message back to the source computer. The source computer processes this ICMP error message to identify the second router and an determine the round trip time for the packet.
The source computer continues to (i) generate packets with TTL fields having higher and higher values, and (ii) send those packets toward the target computer until the target computer finally receives a packet and does not respond with an ICMP error message (e.g., the target computer can respond with an acknowledgement message). The ICMP error messages that the source computer receives prior to reaching the target computer enable the source computer to identify the path leading from the source computer to the target computer (assuming that the path did not change during the route tracing process).